\section{A Multi-mode Trace Signal Selection Algorithm}
\label{sec:algorithm}
We first define a set of metrics which drives our algorithm to identify the
top candidates for multi-mode restoration, and then discuss the selection
procedure using these metrics. Our metrics are defined by extending the
ones for single-mode of operation.

\subsection{Metrics to Find the Top Candidates for Multi-Mode Restoration}
%Recently, the work \cite{LiD13,LiD14TCAD} introduces a new approach to quickly identify the top candidates for tracing in SMTS. The approach is based on a forward-greedy (sequential) selection of trace signals. At each step of identifying the next signal, it efficiently identifies a small number of top candidates by utilizing a blend of metrics which can be quickly evaluated together with X-Simulation (though a very few number of X-Simulations). As a result, it reports both a high solution quality as well as a fast runtime compared to the prior work. Below, we review these metrics (\emph{with extensions for mode consideration}) which we utilize for the MMTS problem.

{\bf Reachability list in a specific mode of operation} is defined as
follows. For a state element $f$ and a specific operation mode $m$, we
define two reachability lists $L^m_{f^v}$ when $f$ takes value $v=0$ and
$v=1$ and the control signals take the values corresponding to mode
$m$. Here $L^m_{f^v}$ is the subset of state elements which can be restored
by $f$ in mode $m$ as explained in Section \ref{sec:rl_sm}. For example in Figure \ref{fig:example}, assume the control signal is set to value $c=0$. For $f_3$ we have  $L^{c=0}_{f_3^0}=\emptyset$ and $L^{c=0}_{f_3^1}=\{f_1,f_2\}$.
We then define a single (merged) reachability list for each operation mode $m=1,\ldots,M$ and each state element $f\in F$ as given below.
\begin{equation}\label{eq:rl}
L^m_f=L^m_{f^0}\cup L^m_{f^1}
\end{equation}
Please note the merged reachability list of a state element in one operation mode may be different than another mode. For example for the circuit in Figure \ref{fig:example}, we have $L^{c=0}_{f_3}=\{f_1,f_2\}$ and $L^{c=1}_{f_3}=\{f_1\}$.

Please note, as stated in Section \ref{sec:rl_sm}, computation of the
reachability lists of all the state elements (for a single operation mode)
is done only once as a pre-processing step prior to trace signal
selection. This computation is fast and can be ignored compared to the
runtime of the trace signal selection procedure \cite{ChatterjeeMB11}.
%\emph{In this work, we compute and make use of (different) reachability lists of each state element \underline{for each operation mode}.}

{\bf Restoration demand in a specific mode of operation} (denoted by
$d^m_{i,f^v}$) is defined between state elements $i$ and $f$ for mode
$m$. Here $i$ is an not-traced state element and $f$ is a candidate
considered for tracing. Furthermore, a subset of the required trace signals
may have already been selected which  (partially) contribute to restoration
of $i$. The restoration demand metric in mode $m$ approximates how much of
the remaining restoration need of $i$ can be provided by $f$, and is
computed by the equation below similar to how it was done in Section \ref{sec:demand}:
\begin{equation}\
d^m_{i,f^v}=\min(1-r_i^m, a_{f^v}^m),~\forall i\in L^m_{f^v}
\label{eq:demand}
\end{equation}
In the above equation $r_i^m$ is the restorability rate of state element
$i$ in mode $m$. (The work \cite{LiD13,LiD14TCAD} shows that these restorability
rates can be computed  for all the state elements quickly, using \emph{one
  round} of X-Simulation in an \emph{observation window} (of 64 cycles)
which is much smaller than the trace buffer's capture window of typically a
few thousand cycles. Therefore computing restorability in multiple
operation modes (after applying mode merging) may also be done quickly.)

{\bf The multi-mode impact weight} is defined as follows. First, we define
the impact weight in mode $m$ using the demand metric in mode $m$ as given below.
\begin{equation}
W^m_f=\sum_{v=0,1}\sum_{\forall i\in L^m_{i,f^v}} d^m_{i,f^v}
\label{eq:impact}
\end{equation}
Finally, we define the multi-mode impact weight ($MW_f$) as below.
\begin{equation}\label{eq:mmiw}\
MW_f=\sum_{m=1}^M{W_f^m}\quad \forall f\in F\setminus T
\end{equation}
It represents the impact weight of state element $f$ over all the modes.

